前言

這次標題不玩梗了，我們腳踏實地的寫文章 - 取而代之，想說這次的主體勉強跟狗拉上關係，每天的 Cover 我們就用狗狗圖來撐版面，圖源都會來自 Bing 的 Image Creator，我會盡量下一些跟主題相關的 Prompt 來生成圖。
一如 Day1 所述，本系列文章的如果牽涉到語言特性會以 C# 為主，特性的部分其他語言的朋友可以參考即可。

資料結構

陣列

• 宣告時決定大小，建立後不可變更，所以無法刪除元素，只能覆蓋為別的元素
• 假設長度為 n 個元素，Index 從 0 開始，到 n - 1

比如 int[3] 就是一個長度為 3 的陣列：
數值 [1,2,3]
Index 0 1 2
當使用 int[0] 取出的數值就會是 1。

今天的圖是一排狗屋，就像陣列一樣，連續蓋在一起。陣列有點像狗屋的概念，狗屋一開始是空的，你可以讓狗狗住進去，狗狗住進去以後就在名牌上寫上名字。當有人來問第三間狗屋裡面住哪隻狗狗，馬上就知道是誰住在裡面了。

針對結構去思考

在遇到 Array 相關的題目，個人的經驗要注意的是：

1. 走訪的順序
   針對走訪整個 Array，for(var i = 0; i < targetArray.Length; i++) 這個 for 迴圈的遍歷式我想大家都寫到爛掉了，但比起立刻決定從頭到尾遍歷，思考一下題目特性，有些題目儘管從前或從後無所謂，但也有題目從尾到頭才有辦法做(反之亦然)，主要在考慮哪個方向更不會遺漏可能的答案。

2. 有序無序
   題目常常會給到提示，資料源是有無排序的，最後回傳的資料需求有沒有一定要排序，有些時候其實這是一種提示，哪些算法跟排序有關，為什麼最後題目出來會是這樣的順序。

3. 時間複雜度
   走訪的時後，如果我們能夠記住哪些東西，或讓可以同時進行的處理同步進行，就可以降低時間複雜度，如雙指針的快慢指針就常常用來處理這件事，藉由定義的速度差或距離差，區隔兩個指針的位置，再讓兩個指針同步前進。

4. 陣列中元素有無重複、結果取用可否重複
   部分演算法使用前需要注意陣列中有無重複元素，會是一個在看題目能夠過濾資訊的點。

相關常用演算法

這邊就是看到如果跟陣列操作/遍歷有關的題目，腦袋裡需要冒出來的選項，我們可以就陣列的結構特性上來連結記住這些演算法。

1. 雙指針(Index操作技巧)
   陣列的其中一個元素就是他的 index，索引 / 下標。決定我們在遍歷陣列的時候，總共需要有幾個變數來記住 index，各個被記住的 index 又有什麼樣的意義呢？雙指針的意思就是有兩個變數來記住兩個不同的 index，從而減少空間複雜度或時間複雜度。雙指針一般有以下兩種：

快慢指針
快慢指針通常會從同向出發，這裡有兩種變型，一種是快的指針走的平均步速就比慢指針快，例如每一個迴圈，慢指針走 n 步，快指針走 2n 步。另一種是快指針的起點先走了 n 步後，慢指針才開始啟動，也就是如果慢指針走了 m 步，快指針此時已經走了 m + n 步。

左右指針
兩個指針一開始會從陣列的頭尾兩邊逐漸往中間靠攏，需要決定什麼樣的情況要移動左指針，什麼樣的情況要移動右指針，當左右指針相遇的時候，表示整個陣列已經被完整遍歷。通常左右指針是用在有序的陣列上，因為此時的左右 index 才有其意義。

2. 滑動窗口(連續元素關係、子序列)
   跟雙指針一樣的是維護兩個指向指針 index 的變數，不一樣的是在這個算法裡面我們關注的是兩個指針中間包含的區域(可以想像，兩個 index)，可能是總和，可能是哪些元素。當我們關注一個陣列中的數個連續元素的關係時，就可能使用滑動窗口。滑動窗口的關鍵在於什麼時後要增大或縮小窗口，以及移動窗口的位置。透過維護這個移動中的指針形成的窗口，往往能夠降低時間複雜度。

3. 前綴和
   依據需求，持續將陣列中的符合條件的元素累加起來的算法，通常用於頻繁累加的狀況，避免每次都要從第一個開始加起。主要是能夠節省時間，應該是相對直覺的演算法，在超時的時候應該會優先想到這個需要優化的部分。

4. 差分陣列
   用於頻繁要對陣列中連續元素做加減的狀況。
   假設陣列有五個元素，依序要對第 1-3 個元素 +2，對第 2-4 個元素 +3，對第 4-5 個元素 -2。一般直線思考就會直接走訪三次目標陣列，並對元素做依序操作。差分陣列的概念在於在原本的陣列外額外維護一個差分陣列，以上面這個例子，會變成 [1] +2 [4] -2, [2] +3 [5] -3, [4] -2，綜合起來變成 [2,3,0,-4,-3] (這個就是差分陣列)，最後從頭開始同步遍歷兩個陣列，維護一個累計的變數比如叫做 diff，遍歷到第 i 個元素時，diff 為差分陣列[1]+差分陣列[2]+...差分陣列[i]的累加，像 2+3-4-3 = -2，到第五個元素的時候 diff = -2，也就正是上面一開始要對第5個元素-2的操作。
   本來時間複雜度需要陣列長度 n * 操作次數 m ，依據 m 的量級，可能接近 O(n^2)，透過差分陣列，能降低到只需要 O(n)。

5. 二分搜尋
   搜尋的演算法其實已經可以自己開一篇了，在入門中相對單純、易懂的就是二分搜尋，陣列相關題目有可能指定使用二分搜尋來解題。二分搜尋有使用前提：陣列中元素必須有序排列，一般題目通常會處理無重覆元素的狀況(但是有序排列的時候，如果有明確指定重複該如何處理，還是能用相近的概念改寫後相容)，使用情境就是在一個陣列中找到指定的某個數出現的位置。
   二分搜尋的概念就是找到陣列正中間的元素(偶數個數時可以偏左偏右，只要確定整體程式邏輯的邊界有定義好，沒有遺漏)，然後看要尋找的目標數比現在正中間的這個元素大還是小，因為是有序，如果要找的比目標大，那就會往右找，反之往左找，直到最後範圍會收縮到目標就是正中間的這個元素，迴圈結束。
   假設陣列為 1,2,3,4,5，二分搜尋目標為 2，那就是先發現 2 < 3，所以往左找切割，剩下 1,2，這時候中間的數字拿到 1， 1 < 2(目標)，所以往右找，右邊剩下 2，也就是目標，找到目標、結案。
   二分搜尋還是算相當基礎的演算法，但最好自己寫過，也要驗算確認自己的算法不會在往左 / 往右選擇邊界的時候遺漏還沒處理的元素。

後面和資料結構相關的文章形式應該會是這樣，一篇介紹大致資料結構牽涉算法，算法大蓋概念、限定情況及解決的問題，下一篇我們會舉一些實際的例子(Leetcode上的題目)來讓大家看實際的程式碼，也能夠實際手寫過確認自己了解概念了。